//https://leetcode.cn/submissions/detail/560661148/
class Solution {
public:
    string minWindow(string s, string t) {
        using ll = long long;
        map<char, ll> cnt1, cnt2;
        ll n1 = s.length(), n2 = t.length();
        s = ' ' + s; t = ' ' + t;
        ll ansl = 0, ansr = n1, l = 1;
        ll mx = 0, cur = 0;
        for (int i = 1; i <= n2; i++)
        {
            if (!cnt2[t[i]])mx++;
            cnt2[t[i]]++;
        }
        for (int r = 1; r <= n1; r++)
        {
            cnt1[s[r]]++; if (cnt2[s[r]] && cnt1[s[r]] == cnt2[s[r]])cur++;
            while (cur == mx)
            {
                if (cur == mx && r - l + 1 < ansr - ansl + 1)ansr = r, ansl = l;
                if (cnt2[s[l]] && cnt1[s[l]] == cnt2[s[l]])cur--;
                cnt1[s[l]]--, l++;
            }
        }

        if (!ansl)return "";
        string ans;
        for (int i = ansl; i <= ansr; i++)ans += s[i];
        return ans;
    }
};